package Top200;

/**
 * @author zhangmin
 * @create 2022-02-22 10:20
 */
public class isMatch44 {
    int[][] memo; //0未计算，-1位false，1为true
    boolean isMat(String s,int i,String p,int j){
        int m=s.length(),n=p.length();
        if (j==n) {
            //p串匹配完，需要s串也匹配完
            return i==m;
        }
        if (i==m){
            //s串匹配完，需要判断p后面的部分是否可以匹配空串
            for (; j < n; j++) {
                if (p.charAt(j)!='*') return false;
            }
            return true;
        }
        if (memo[i][j]!=0){
            return memo[i][j]==1;
        }
        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='?'){
            //s[i] p[j]匹配成功
            res=isMat(s,i+1,p,j+1);
        }else {
            if (p.charAt(j)=='*'){
                //跳过重复的*，直到最后一个*的位置，多个连续*和一个*一样
                while (j+1<n&&p.charAt(j+1)=='*'){
                    j++;
                }
                //此时*可以匹配多次或0次
                res=isMat(s,i,p,j+1)||isMat(s,i+1,p,j);
            }
        }
        memo[i][j]=res?1:-1;

        return res;
    }
    public boolean isMatch(String s, String p) {
        memo=new int[s.length()][p.length()];

        return isMat(s,0,p,0);
    }
}
